package _07;

import java.util.*;
/**
 * Good Question.
 */
public class Solution {
    public static BitInteger[] init(int n, int[] missing) {
	BitInteger[] array = new BitInteger[n];
	int lucky = (int)((n + 1) * Math.random());
	missing[0] = lucky;
	int increment = 0;
	for (int i = 0; i < n; i++) {
	    if (i == lucky) {
//		i++;
	    	increment = 1;
//		continue;
	    } 
		array[i] = new BitInteger(i + increment);
	}
	shuffle(array);
	return array;
    }

    /**
     * Good Question. Pay attention to the <E> position.
     * Between static and return type.
     */
    private static <E> void shuffle(E[] arr) {
	int len = arr.length;
	for (int i = 0; i < len; i++) {
	    int index = i + (int)((len - i) * Math.random());
	    if (index != i) {
		E tmp = arr[i];
		arr[i] = arr[index];
		arr[index] = tmp;
	    }
	}
    }

    public static int find(BitInteger[] arr) {
	int N = arr.length;
	List<BitInteger> list = new ArrayList<BitInteger>();
	for (int i = 0; i < N; i++)
		list.add(arr[i]);
	int[] wrapper = new int[1];
//		{0};
//	int result = 
			find(list, 31, wrapper);
			return wrapper[0];
    }

    private static void find(List<BitInteger> list, int index, int[] result) {
	if (index < 0) {
	    return;
//	    result[0];
	}
	List<BitInteger> ones = new ArrayList<BitInteger>();
	List<BitInteger> zeros = new ArrayList<BitInteger>();
//	for (Iterator<BitInteger> iter = list.iterator(); iter.hasNext();) {
//	    BitInteger BI = iter.next();
	for (int i = 0; i < list.size(); i++) {
		BitInteger BI = list.get(i);
	    if (BI.fetch(index) == 1) {
		ones.add(BI);
	    } else {
		zeros.add(BI);
	    }
	}
	if (zeros.size() <= ones.size()) {
	    result[0] &= ~(1 << (31 - index));
//	    return
	    find(zeros, index-1, result);
	} else {
	    result[0] |= (1 << (31 - index));
//	    return
	    find(ones, index - 1, result);
	}
    }

    public static void main(String[] args) {
	int N = 20;
	int[] missing = new int[1];
	int result = find(init(N, missing));
	System.out.println("result is: " + result);
	System.out.println("missing is actually: " + missing[0]);
    }
}

class BitInteger {
    public static final int INT_SIZE = 32;
    boolean[] bits;

    public BitInteger() {
	bits = new boolean[INT_SIZE];
    }

    public BitInteger(int value) {
	this();
	for (int i = 0; i < INT_SIZE; i++) {
	    if ((value & (1 << i)) > 0)
		bits[INT_SIZE - 1 - i] = true;
	    else
		bits[INT_SIZE-1-i] = false;
	}
    }

    /** Return k-th most-significent bit */
    public int fetch(int k) {
	if (bits[k])
	    return 1;
	else
	    return 0;
    }

    public void set(int k, int bitValue) {
	if (bitValue == 0)
	    bits[k] = false;
	else
	    bits[k] = true;
    }

    public void set(int k, char bitValue) {
	if (bitValue == '0')
	    bits[k] = false;
	else
	    bits[k] = true;
    }

    public void set(int k, boolean bitValue) {
	bits[k] = bitValue;
    }

    public int toInteger() {
	int result = 0;
	for (int i = INT_SIZE - 1; i >= 0; i--) {
	    if (bits[i])
		result |= (1 << (INT_SIZE - 1 -i));
	}
	return result;
    }
    
    public String toString() {
    	StringBuffer sb = new StringBuffer();
    	for (int i = 0; i < INT_SIZE; i++) {
    		if (bits[i]) {
    			sb.append('1');
    		} else {
    			sb.append('0');
    		}
    	}
    	return sb.toString();
    }
}